Introductie

Good Old-Fashioned AI

• Symbolische/klassieke AI
• Kennis van de wereld is uitgedrukt in simpele regels
• AI combineert regels om nieuwe conclusies te trekken

Voorbeeld van regels

• Een muur is een obstakel
• Een gesloten deur is een obstakel
• Een open deur is geen obstakel
• Een gesloten deur kan worden geopend met een deurklink
• Een open deur biedt de doorgang naar de volgende kamer

Representatie

GOFAI in games

• Pathfinding
  • Dijkstra’s algoritme
  • A*
• Planning
  • GOAP
  • Decision trees
• Bruteforce
  • Minimax
  • Deep Blue

Pathfinding (A*)

Pathfinding (A*)

Planning (GOAP)

• Goal-Oriented Action Planning
• Representeer de omgeving als een reeks variabelen
• Gebruik acties om de omgevingsstaat te veranderen

Minimax

• Tegenstander probeert eigen score te maximaliseren
• Kies een actie die tegenstander’s score minimaliseert
• Zero-sum: jouw winst is mijn verlies
• Representatie is de score en mogelijke acties

Tekortkomingen

• Representatie van de wereld
• Sommige methodes hebben handgeschreven regels nodig
• Niet flexibel

AI Winter

• Belofte van menselijke intelligentie
• AI bleek niet te generaliseren
• Investeringen stopten

Machine Learning

Een alternatief voor GOFAI

• Leer nuttige representaties van ervaringen
• Geen kennis van achterliggend proces
• Geen wondermiddel
  • Nieuwe oplossingen
  • Ook nieuwe problemen

Hoe leren machines?

• Computerwetenschap
• Statistiek
• Biologie

Biologische inspiratie

• Hersenen kunnen leren van ervaringen/voorbeelden
• Niet bekend hoe dit werkt
• Bouw een brein en kijk hoe ver je komt

Kunstmatig brein

• Brein is opgebouwd uit neuronen
• Maak een kunstmatig neuron en bouw een kunstmatig brein

Neuron

Benodigdheden kunstmatig neuron

• Ontvang signalen van verschillende sterktes
• Combineer signalen en vergelijk met drempelwaarde
• Pas signaalsterktes aan om te “leren”

Supervised learning

Perceptron

• Afbeeldingen van 20x20 pixels
• Elke pixel (waarde tussen 0 en 1) is een signaal
• Output signaal is een voorspelling

Afbeelding als signalen

• Elke pixel een waarde tussen \(0\) (zwart) en \(1\) (wit)
• Kleurenafbeelding als drie aparte zwart wit afbeeldingen (drie RGB kanalen)

Activatiefunctie

• Simuleert de drempelwaarde
• Logistieke functie \(\sigma(x)=\frac{1}{1+e^{-x}}\)
• Waarde hoger dan \(0.5\rightarrow1\) anders \(0\)

Leren

• Data \(\mathbf{x}=x_1, x_2, \cdots, x_N\) en \(\mathbf{y}=y_1, y_2, \cdots, y_N\)
• Parameters \(\mathbf{w}=w_1, w_2, \cdots, w_D\)
• Error/loss functie \(L_\mathbf{w}(\mathbf{x}, \mathbf{y})=\frac{1}{N}\sum_{n=1}^N(h_{\mathbf{w}}(x_n) - y_n)^2\)
• Pas parameters aan om error zo klein mogelijk te maken

Eenvoudiger voorbeeld

• Voorspel het weer met sensoren
• Input signalen: temperatuur (graden celsius), windsnelheid (km/h), luchtvochtigheid (%)
• Output/voorspellingen: zonnig (\(1\)), regenachtig (\(0\))

Een datapunt

• \(x_n = [12.3, 34.8, 75.1]\)
• \(y_n = 0\)
• \(\mathbf{w} = [0.1, 0.04, -0.03]\)
• \[\begin{eqnarray}h_\mathbf{w}(x_n)&=&\sigma(0.1\cdot12.3+0.04\cdot34.8-0.03\cdot75.1) \\ &\approx&0.591\end{eqnarray}\]
• \(l_n=(0.591 - 0)^2\approx0.350\)
• Herhaal voor alle datapunten en bereken gemiddelde error

Random search

• Begin met willekeurige parameters \(\mathbf{w}^*=\mathbf{w}\)
• Bereken error \(L^*=L_\mathbf{w}(\mathbf{x}, \mathbf{y})\) voor de dataset
• Genereer nieuwe parameters \(\mathbf{w}'\) met bijbehorende \(L'\)
• Als \(L'<L^*\) update: \(\mathbf{w}^*\leftarrow\mathbf{w}'\) en \(L^*\leftarrow L'\)
• Herhaal vorige twee stappen tot gewenst resultaat

Random search

• Erg traag; hoge variantie
• Alle mogelijke waardes van \(\mathbf{w}\) moeten uitgeprobeerd worden
• \(2^{64}\) waardes voor elk element van \(\mathbf{w}\)
• Voor drie dimenties is dat \(2^{192}\approx6.28\cdot10^{57}\)
• Afbeeldingen voor de perceptron hebben \(400\) dimensies 🙃

Optimalisatie

• Parameters met goede performance liggen dicht bij elkaar
• Maak gebruik van de ‘vorm’ van de error functie
• Volg de helling naar een dieptepunt

Gradient Descent

• Gebruik de afgeleide van de functie \(L_\mathbf{w}(\mathbf{x}, \mathbf{y})\)
• Hoe verandert de error \(L_\mathbf{w}\) als we parameters \(\mathbf{w}\) veranderen?
• Afgeleide/gradient

Deep Learning

• Netwerk van neuronen vormt een brein
• Netwerk van Perceptrons vormt een Multi-Layered Perceptron
• (Deep) Neural Network

Neuraal Netwerk

• Twee input neuronen
• Vijf verborgen (hidden) neuronen
• Een output neuron

Neuraal Netwerk

• Trainen met Gradient Descent en Backpropagation
• Bereken de uitkomst van het netwerk (forward propagation)
• Herleid de afgeleiden van de parameters laag voor laag terug van de output (back propagation)

Diep Neuraal Netwerk

• Kan alles leren met genoeg* verborgen neuronen in 1 laag
• Plak meerdere verborgen lagen achter elkaar
• Diepere netwerken zijn efficienter en complexer dan brede netwerken

Deep Learning Renaissance

• Backpropagation was uitgevonden in 1986
• Deep learning werd populair in 2012
• Tekort aan data en rekenkracht

Deep Learning Renaissance

• Data tekort \(\rightarrow\) internet (social media)
• Rekenkracht \(\rightarrow\) videokaarten

Toepassingen van supervised learning

• Diagnostiek (analyse van röntgen, EEG, etc.)
• Speech-to-text
• Gezichtsherkenning

Self-learning AI in Games

• Supervised learning; voornamelijk voor demonstratie van nieuwe netwerkstructuren
• Reinforcement learning; zelflerende “agenten” in games
• Unsupervised learning; genereer nieuwe data adhv aangegeven eisen (procedural content generation)

Agenda

• Twee delen
• Reinforcement learning
• Unsupervised learning
• Jullie suggesties?

Huiswerkopdrachten

• Python
• OpenAI Gym
• Deadline de dag voor de volgende opdracht